package com.lfg.leetcode.leetcode1000;


import java.util.HashMap;
import java.util.Map;

public class No1143longestCommonSubsequence {
    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde","ace"));
    }

    public static int longestCommonSubsequence(String text1, String text2) {
        int length2 = text2.length()+1;
        int length1 = text1.length()+1;
        int[][] dp = new int[length1][length2];
        for(int i = 1; i<length1; i++){
            for (int j = 1; j < length2; j++) {
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[length1-1][length2-1];
    }

}

